package com.cherrish.demo.algorithm.tree.bintree;

import com.cherrish.demo.algorithm.tree.Tree;

/**
 * @author oxchains
 * @time 2019-02-20 16:25
 * @name BinTree
 * @desc:
 */
public class BinTree implements Tree {

    private Node root;


    @Override
    public Node find(int key) {
        Node current = root;
        while (null != current){
            if(current.data > key){
                current = current.left;
            }else if(current.data < key){
                current = current.right;
            }else if(current.data == key){
                return current;
            }
        }
        return null;
    }

    @Override
    public boolean insert(int key) {
        Node newNode = new Node(key);
        if(null == root){
            root = newNode;
            return true;
        }else {
            Node current = root;
            Node parent = null;
            while (null != current){
                parent = current;
                if(current.data > key){
                    current = current.left;
                    if(null == current){
                        parent.left = newNode;
                        return true;
                    }
                } else {
                    current = current.right;
                    if(null == current){
                        parent.right = newNode;
                        return true;
                    }
                }
            }
        }
        return false;
    }

    @Override
    public boolean delete(int key) {
        Node current = root;
        Node parent = root;
        boolean isLeft = false;
        while (current.data != key){
            parent = current;
            if(current.data > key){
                isLeft = true;
                current = current.left;
            }else {
                isLeft = false;
                current = current.right;
            }
            if(null == current){
                return false;
            }
        }
        return false;
    }

    @Override
    public void infixOrder(Node node) {
        if(null != node){
            infixOrder(node.left);
            System.out.print(node.data +" ");
            infixOrder(node.right);
        }
    }

    @Override
    public void preOrder(Node node) {
        if(null != node){
            System.out.print(node.data +" ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    @Override
    public void postOrder(Node node) {
        if(null != node){
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.data +" ");
        }
    }

    @Override
    public Node findMin() {
        Node current = root;
        Node min = current;
        while (null != current){
            min = current;
            current = current.left;
        }
        return min;
    }

    @Override
    public Node findMax() {
        Node current = root;
        Node max = current;
        while (null != current){
            max = current;
            current = current.right;
        }
        return max;
    }

    public static void main(String[] args) {
        BinTree bt = new BinTree();
        bt.insert(50);
        bt.insert(20);
        bt.insert(80);
        bt.insert(10);
        bt.insert(0);
        bt.insert(3);
        bt.insert(90);
        bt.insert(25);
        bt.insert(125);
        bt.insert(25);
        bt.insert(185);
        bt.insert(100);
        //bt.delete(10);//删除没有子节点的节点
        //bt.delete(30);//删除有一个子节点的节点
        //bt.delete(80);//删除有两个子节点的节点
        System.out.println(bt.findMax().data);
        System.out.println(bt.findMin().data);
        System.out.println(bt.find(100));
        System.out.println(bt.find(200));

        bt.preOrder(bt.root);
        System.out.println();
        bt.infixOrder(bt.root);
        System.out.println();
        bt.postOrder(bt.root);
    }
}
